home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Moscow ML 1.42 / lib / Binarymap.sig < prev    next >
Encoding:
Text File  |  1997-08-18  |  2.7 KB  |  72 lines  |  [TEXT/Moml]
  1. (* Binarymap -- applicative maps implemented by balanced ordered binary trees.
  2.  *
  3.  * Modified for Moscow ML from SML/NJ library v. 0.2 which is 
  4.  * COPYRIGHT (c) 1993 by AT&T Bell Laboratories.  
  5.  * See file mosml/copyrght/copyrght.att for details.
  6.  * Original implementation due to Stephen Adams, Southampton, UK.
  7.  *)
  8.  
  9. type ('key, 'a) dict
  10.  
  11. exception NotFound
  12.  
  13. val mkDict    : ('key * 'key -> order) -> ('key, 'a) dict
  14. val insert    : ('key, 'a) dict * 'key * 'a -> ('key, 'a) dict
  15. val find      : ('key, 'a) dict * 'key -> 'a
  16. val peek      : ('key, 'a) dict * 'key -> 'a option
  17. val remove    : ('key, 'a) dict * 'key -> ('key, 'a) dict * 'a
  18. val numItems  : ('key, 'a) dict -> int
  19. val listItems : ('key, 'a) dict -> ('key * 'a) list
  20. val app       : ('key * 'a -> unit) -> ('key,'a) dict -> unit
  21. val revapp    : ('key * 'a -> unit) -> ('key,'a) dict -> unit
  22. val foldr     : ('key * 'a * 'b -> 'b)-> 'b -> ('key,'a) dict -> 'b
  23. val foldl     : ('key * 'a * 'b -> 'b) -> 'b -> ('key,'a) dict -> 'b
  24. val map       : ('key * 'a -> 'b) -> ('key,'a) dict -> ('key, 'b) dict
  25. val transform : ('a -> 'b) -> ('key,'a) dict -> ('key, 'b) dict
  26.  
  27.  
  28. (* Type ('key, 'a) dict is the type of applicative maps from domain
  29.    type 'key to range type 'a, or equivalently, applicative
  30.    dictionaries with keys of type 'key and values of type 'a.  They
  31.    are implemented as ordered balanced binary trees.
  32.  
  33.    [mkDict ordr] returns a new, empty map whose keys have ordering
  34.    ordr.
  35.  
  36.    [insert(m, i, v)] extends (or modifies) map m to map i to v.
  37.  
  38.    [find (m, k)] returns v if m maps k to v; otherwise raises NotFound.
  39.    
  40.    [peek(m, k)] returns SOME v if m maps k to v; otherwise returns NONE.
  41.  
  42.    [remove(m, k)] removes k from the domain of m and returns the
  43.    modified map and the element v corresponding to k.  Raises NotFound
  44.    if k is not in the domain of m.
  45.  
  46.    [numItems m] returns the number of entries in m (that is, the size
  47.    of the domain of m).
  48.  
  49.    [listItems m] returns a list of the entries (k, v) of keys k and
  50.    the corresponding values v in m.
  51.  
  52.    [app f m] applies function f to the entries (k, v) in m, in
  53.    increasing order of k (according to the ordering ordr used to
  54.    create the map or dictionary).
  55.  
  56.    [revapp f m] applies function f to the entries (k, v) in m, in
  57.    decreasing order of k.
  58.  
  59.    [foldl f e m] applies the folding function f to the entries (k, v)
  60.    in m, in increasing order of k.
  61.  
  62.    [foldr f e m] applies the folding function f to the entries (k, v)
  63.    in m, in decreasing order of k.
  64.  
  65.    [map f m] returns a new map whose entries have form (k, f(k,v)),
  66.    where (k, v) is an entry in m.
  67.  
  68.    [transform f m] returns a new map whose entries have form (k, f v),
  69.    where (k, v) is an entry in m.
  70.  
  71. *)
  72.